package com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20241006;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class leetcode3310 {

    /**
     * 移除可疑的方法，k为bug方法，它直接调用或间接调用的任何方法都被视为可疑方法
     * @param n
     * @param k
     * @param invocations
     * @return
     */
    public List<Integer> remainingMethods(int n,int k,int[][] invocations){
        List<Integer>[] g=new ArrayList[n];// 链表数组
        Arrays.setAll(g,i->new ArrayList<>());
        for(int[] e : invocations){
            g[e[0]].add(e[1]);
        }

        // 标记所有可疑方法
        boolean[] isSuspicious=new boolean[n];
        dfs(k,g,isSuspicious);

        // 检查是否有非可疑方法->可疑方法
        for(int[] e : invocations){
            // e[0]->e[1]
            if(!isSuspicious[e[0]] && isSuspicious[e[1]]){
                // 无法移除可疑方法
                List<Integer> ans=new ArrayList<>(n);
                for(int i=0;i<n;i++){
                    ans.add(i);
                }
                return ans;
            }
        }

        // 移除所有可疑方法，构建结果集
        List<Integer> ans=new ArrayList<>();
        for(int i=0;i<n;i++){
            if(!isSuspicious[i]){
                ans.add(i);
            }
        }
        return ans;
    }

    // dfs遍历
    private void dfs(int x,List<Integer>[] g,boolean[] isSuspicious){
        isSuspicious[x]=true;
        for(int y : g[x]){
            if(!isSuspicious[y]){// 避免无限递归
                dfs(y,g,isSuspicious);
            }
        }
    }
}
